﻿#define _CRT_SECURE_NO_WARNINGS 1
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。



示例 1：


输入：head = [1, 2, 2, 1]
输出：true
示例 2：


输入：head = [1, 2]
输出：false


提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9


进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https ://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //思路:先将链表的数据用数组存储起来 1.再将链表反转，进行比较，如果中途不相等，就返回false
 //                               2.直接采用双指针对该数组判断
    bool isPalindrome(struct ListNode* head) {
    struct ListNode* cur = head;

    int numsSize = 0;
    while (cur)
    {
        cur = cur->next;
        numsSize++;
    }
    int* arr = (int*)malloc(sizeof(int) * (numsSize + 1));
    cur = head;
    int i = 0;
    while (cur)
    {
        arr[i++] = cur->val;
        cur = cur->next;
    }

    struct ListNode* n1 = NULL, * n2 = head, * n3 = head->next;
    while (n2)
    {
        //反转链表
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    i = 0;
    while (n1)
    {
        if (arr[i++] != n1->val)
        {
            return false;
        }
        n1 = n1->next;
    }
    free(arr);
    arr = NULL;
    return true;


}